# DS Graph - javatpoint
# https://www.javatpoint.com/ds-graph

try:
    import graphviz
except ImportError:
    graphviz = None

class GraphNode:
    """
    GraphNode represents a node in a graph.

    Attributes:
        data: Data stored in the node.
        parents: List of parent nodes.
        children: List of child nodes.
    """

    def __init__(self, data=None):
        """
        Initialize a GraphNode with data and empty lists of parents and children.

        Args:
            data: Initial data for this node. Defaults to None.
        """
        self.data = data
        self.parents = []
        self.children = []

    def add_parent(self, parent):
        """
        Add a parent node to the current node.

        Args:
            parent: Parent node to be added.
        """
        self.parents.append(parent)

    def remove_parent(self, parent):
        """
        Remove a parent node from the current node.

        Args:
            parent: Parent node to be removed.
        """
        self.parents.remove(parent)

    def add_child(self, child):
        """
        Add a child node to the current node.

        Args:
            child: Child node to be added.
        """
        self.children.append(child)

    def remove_child(self, child):
        """
        Remove a child node from the current node.

        Args:
            child: Child node to be removed.
        """
        self.children.remove(child)

    def is_leaf(self):
        """
        Check if the current node is a leaf node.

        Returns:
            True if the node is a leaf, False otherwise.
        """
        return len(self.children) == 0

    def is_internal(self):
        """
        Check if the current node is an internal node.

        Returns:
            True if the node is internal, False otherwise.
        """
        return len(self.children) > 0


class Graph:
    """
    Graph represents a graph data structure.

    Attributes:
        nodes: List of nodes in the graph.
    """

    def __init__(self):
        """
        Initialize an empty graph with no nodes.
        """
        self.nodes = []

    def add_node(self, data):
        """
        Add a node to the graph.

        Args:
            data: Data for the node.
        """
        node = GraphNode(data)
        self.nodes.append(node)

    def remove_node(self, node):
        """
        Remove a node from the graph.

        Args:
            node: Node to be removed.
        """
        if node in self.nodes:
            self.nodes.remove(node)
            for parent in node.parents:
                parent.remove_child(node)
            for child in node.children:
                child.remove_parent(node)

    def add_edge(self, parent, child):
        """
        Add an edge between two nodes in the graph.

        Args:
            parent: Parent node.
            child: Child node.
        """
        parent.add_child(child)
        child.add_parent(parent)

    def remove_edge(self, parent, child):
        """
        Remove an edge between two nodes in the graph.

        Args:
            parent: Parent node.
            child: Child node.
        """
        parent.remove_child(child)
        child.remove_parent(parent)

    def get_nodes(self):
        """
        Get a list of nodes in the graph.

        Returns:
            List of nodes.
        """
        return self.nodes

    def breadth_first_traversal(self):
        """
        Perform breadth-first traversal of the graph and print the node values.
        """
        if not self.nodes:
            return
        visited = set()
        queue = []
        for node in self.nodes:
            if node not in visited:
                queue.append(node)
                visited.add(node)
                while queue:
                    current_node = queue.pop(0)
                    print(current_node.data)
                    for child in current_node.children:
                        if child not in visited:
                            queue.append(child)
                            visited.add(child)

    def depth_first_traversal(self):
        """
        Perform depth-first traversal of the graph and print the node values.
        """
        if not self.nodes:
            return
        visited = set()
        stack = []
        for node in self.nodes:
            if node not in visited:
                stack.append(node)
                visited.add(node)
                while stack:
                    current_node = stack.pop()
                    print(current_node.data)
                    for child in current_node.children:
                        if child not in visited:
                            stack.append(child)
                            visited.add(child)

    def size(self):
        """
        Calculate the size (number of nodes) of the graph.

        Returns:
            Size of the graph.
        """
        return len(self.nodes)

    def height(self):
        """
        Calculate the height of the graph.

        Returns:
            Height of the graph.
        """
        if not self.nodes:
            return 0
        heights = []
        for node in self.nodes:
            if node.is_leaf():
                heights.append(1)
            else:
                heights.append(self._height_helper(node))
        return max(heights)

    def _height_helper(self, node):
        """
        Helper method for calculating the height of a node.

        Args:
            node: Current node being visited.

        Returns:
            Height of the subtree rooted at the current node.
        """
        if node.is_leaf():
            return 1
        heights = []
        for child in node.children:
            heights.append(self._height_helper(child))
        return max(heights) + 1

    def depth(self, node):
        """
        Calculate the depth of a node in the graph.

        Args:
            node: Node for which to calculate the depth.

        Returns:
            Depth of the node.
        """
        return self._depth_helper(node, 0)

    def _depth_helper(self, node, depth):
        """
        Helper method for calculating the depth of a node in the graph.

        Args:
            node: Current node being visited.
            depth: Current depth in the graph.

        Returns:
            Depth of the node.
        """
        if not node.parents:
            return depth
        parent = node.parents[0]
        return self._depth_helper(parent, depth + 1)

    def is_internal_node(self, node):
        """
        Check if a given node is an internal node.

        Args:
            node: Node to check.

        Returns:
            True if the node is internal, False otherwise.
        """
        return node.is_internal()

    def _display_helper(self, node, indent="", last=True, visited=None):
        """
        Helper method to construct the string representation of the graph.

        Args:
            node: Current node being visited.
            indent: Indentation string.
            last: True if the current node is the last child, False otherwise.

        Returns:
            Lines representing the graph.
        """
        lines = []

        if node not in visited:
            prefix = "`-- " if last else "|-- "
            lines.append(indent + prefix + str(node.data))
            child_count = len(node.children)
            for i, child in enumerate(node.children):
                if child in visited:
                    continue
                is_last = (i == child_count - 1)
                child_indent = "    " if last else "|   "
                line = self._display_helper(child, indent + child_indent, is_last, visited=visited)
                visited.add(child)
                if line:
                    lines.extend(line)
        return lines

    def __str__(self):
        """
        Returns a string representation of the graph.

        Returns:
            A string representation of the graph.
        """
        if not self.nodes:
            return "Empty Graph"

        lines = []
        visited = set()
        for i, node in enumerate(self.nodes):
            is_last = (i == len(self.nodes) - 1)
            line = self._display_helper(node, last=is_last, visited=visited)
            if line:
                lines.extend(line)
        return "\n".join(lines)

if __name__ == "__main__":
    # Create a new graph
    my_graph = Graph()

    # Add nodes to the graph
    my_graph.add_node("A")
    my_graph.add_node("B")
    my_graph.add_node("C")
    my_graph.add_node("D")
    my_graph.add_node("E")
    my_graph.add_node("F")

    # Add edges between nodes
    my_graph.add_edge(my_graph.get_nodes()[0], my_graph.get_nodes()[1])
    my_graph.add_edge(my_graph.get_nodes()[0], my_graph.get_nodes()[2])
    my_graph.add_edge(my_graph.get_nodes()[0], my_graph.get_nodes()[3])
    my_graph.add_edge(my_graph.get_nodes()[1], my_graph.get_nodes()[4])
    my_graph.add_edge(my_graph.get_nodes()[1], my_graph.get_nodes()[5])

    # Print the graph structure
    print("Graph structure:")
    print(my_graph)
    # Output:
    # Graph structure:
    # |-- A
    # |   |-- B
    # |   |   |-- E
    # |   |   `-- F
    # |   |-- C
    # |   `-- D
    # |-- B
    # |   |-- E
    # |   `-- F
    # |-- C
    # |-- D
    # |-- E
    # `-- F

    # Perform breadth-first traversal
    print("Breadth-first traversal:")
    my_graph.breadth_first_traversal()
    # Output:
    # A
    # B
    # C
    # D
    # E
    # F

    # Perform depth-first traversal
    print("Depth-first traversal:")
    my_graph.depth_first_traversal()
    # Output:
    # A
    # D
    # C
    # B
    # F
    # E

    # Get the size of the graph
    graph_size = my_graph.size()
    print("Graph size:", graph_size)
    # Output:
    # Graph size: 6

    # Get the height of the graph
    graph_height = my_graph.height()
    print("Graph height:", graph_height)
    # Output:
    # Graph height: 3

    # Calculate the depth of a node
    node_depth = my_graph.depth(my_graph.get_nodes()[4])
    print("Depth of node 'E':", node_depth)
    # Output:
    # Depth of node 'E': 2

    # Check if a node is internal
    node_a = my_graph.get_nodes()[0]
    print(f"Is node '{node_a.data}' internal? {my_graph.is_internal_node(node_a)}")
    # Output:
    # Is node 'A' internal? True

    # Remove a node from the graph
    my_graph.remove_node(my_graph.get_nodes()[2])

    # Print the graph structure after removing a node
    print("Graph structure after removing a node:")
    print(my_graph)
    # Output:
    # Graph structure after removing a node:
    # |-- A
    # |   |-- B
    # |   |   |-- E
    # |   |   `-- F
    # |   `-- D
    # |-- B
    # |   |-- E
    # |   `-- F
    # |-- D
    # |-- E
    # `-- F

